﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Stone
{
    class MapRouteEngine
    {
        List<MapConnection> _connections;
        List<MapNode> _locations;

        public List<MapNode> Locations
        {
            get { return _locations; }
            set { _locations = value; }
        }
        public List<MapConnection> Connections
        {
            get { return _connections; }
            set { _connections = value; }
        }

        public MapRouteEngine()
        {
            _connections = new List<MapConnection>();
            _locations = new List<MapNode>();
        }

        /// <summary>
        /// Calculates the shortest MapRoute to all the other MapNode
        /// </summary>
        /// <param name="_startLocation"></param>
        /// <returns>List of all MapNode and their shortest MapRoute</returns>
        public Dictionary<MapNode, MapRoute> CalculateMinCost(MapNode _startLocation)
        {
            //Initialise a new empty MapRoute list
            Dictionary<MapNode, MapRoute> _shortestPaths = new Dictionary<MapNode, MapRoute>();

            //Initialise a new empty handled MapNode list
            List<MapNode> _handledLocations = new List<MapNode>();

            //Initialise the new routes. the constructor will set the route weight to in.max
            foreach (MapNode location in _locations)
            {
                _shortestPaths.Add(location, new MapRoute(location.Name));
            }

            //The startPosition has a weight 0. 
            _shortestPaths[_startLocation].Cost = 0;

            //If all locations are handled, stop the engine and return the result
            while (_handledLocations.Count != _locations.Count)
            {
                //Order the locations
                List<MapNode> _shortestLocations = (List<MapNode>)(from s in _shortestPaths
                                                                   orderby s.Value.Cost
                                                                   select s.Key).ToList();
                MapNode _locationToProcess = null;

                //Search for the nearest location that isn't handled
                foreach (MapNode _location in _shortestLocations)
                {
                    if (!_handledLocations.Contains(_location))
                    {
                        //If the cost equals int.max, there are no more possible connections to the remaining locations
                        if (_shortestPaths[_location].Cost == int.MaxValue)
                            return _shortestPaths;

                        _locationToProcess = _location;
                        break;
                    }
                }

                //Select all connections where the startposition is the location to Process
                var _selectedConnections = from c in _connections
                                           where c.A == _locationToProcess
                                           select c;

                //Iterate through all connections and search for a connection which is shorter
                foreach (MapConnection conn in _selectedConnections)
                {
                    if (_shortestPaths[conn.B].Cost > conn.Weight + _shortestPaths[conn.A].Cost)
                    {
                        _shortestPaths[conn.B].Connections = _shortestPaths[conn.A].Connections.ToList();
                        _shortestPaths[conn.B].Connections.Add(conn);
                        _shortestPaths[conn.B].Cost = conn.Weight + _shortestPaths[conn.A].Cost;
                    }
                }
                //Add the location to the list of processed locations
                _handledLocations.Add(_locationToProcess);
            }

            return _shortestPaths;
        }
    }
}
